#include <stdio.h>
#include <stdlib.h>
#define MAX_LEN 100

//查找
/*


*/

//顺序查找O(n)
typedef struct
{
    int *elem;     //动态数组基地
    int TablenLen; //表长
} SSTable;

int Search_Seq(SSTable ST, int key)
{
    int i = 0;
    for (i = 0; i < ST.TablenLen && ST.elem[i] != key; ++i)
    {
    }
    return i == ST.TablenLen ? -1 : i;
}

//哨兵
int Search_Seq2(SSTable ST, int key)
{
    ST.elem[0] = key; //数组从第1个位置存储元素，第0个位置作为哨兵
    int i = 0;
    for (i = ST.TablenLen; ST.elem[i] != key; --i)
    {
    }
    return i;
}
//顺序查找的优化
/*
1、若顺序表有序，当前关键字大于（或小于）目标关键字，查找失败  降低查找失败时候的ASL（平均查找长度）
2、按各个关键字被查找概率不同降序排列  降低查找成功时候的ASL
*/

//折半查找
/*
针对有序序列



*/
int Binary_Search(SSTable L, int key)
{
    int low = 0, high = L.TablenLen - 1, mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (L.elem[mid] == key)
        {
            return mid;
        }
        else if (L.elem[mid] > key)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}
//折半查找二叉树
/*
一定是一棵平衡二叉树


mid = (low + high) / 2  向下取整
右子树结点数-左子树结点数=0或1
mid = (low + high) / 2  向上取整
左子树结点数-右子树结点数=0或1

只有最下面一层是不满的
树高log2(n+1) 向上取整

失败结点：n+1（等于成功结点的空链域数量）

*/



//分块查找
/*
索引表中保存每个分块中最大关键字和分块的存储区间




*/



int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}